The previous slide demonstrated the core mechanism of Bubble Sort: comparing adjacent elements and swapping them to move the largest element to the right. We now trace the detailed execution of the first pass ($i=0$) using our Example Array, $A = [8, 2, 5, 1, 6]$, where $n=5$.

  • The first pass requires $n-1 = 4$ comparisons (indexed $j=0$ to $j=3$). In each comparison, if $A[j] > A[j+1]$, a swap occurs, ensuring that the larger element continues to move right.
  • By the end of this pass, the element 8 (the largest in $A$) is guaranteed to be fixed in the final position $A[4]$, forming the initial sorted suffix.
  • Subsequent passes only compare elements in the remaining unsorted prefix $A[0..n-2]$.
  • The inner loop performs $O(n)$ comparisons per pass, leading to the overall $O(n^2)$ time complexity for Bubble Sort.
Python Implementation: Bubble Sort Inner Loop
1def bubble_sort(A):
2    n = len(A)
3    for i in range(n - 1): # Outer loop (Passes)
4        for j in range(n - 1 - i): # Inner loop (Comparisons)
5            if A[j] > A[j+1]:
6                A[j], A[j+1] = A[j+1], A[j] # Swap
7    return A